package tree.structure;

import java.util.*;

/**
 * @user 26233
 * @create 2020-03-15 22:11:16
 * @description
 **/

public class TreeUtil<T> {

    // 树元素
    T[] nodeData;
    public TreeUtil() {
    }
    public TreeUtil(T[] nodeData) {
        this.nodeData = nodeData;
    }
    /**
     * 根据数组元素 创建树结构
     * @param nodeData
     * @param nullFlag
     * @return
     */
    public TreeNode<T> createTree(T[] nodeData, T nullFlag, int index){
        if(nodeData == null || nodeData.length < 1)
            return null;
        if(index < nodeData.length && !nodeData[index].equals(nullFlag)){
            TreeNode<T> node = new TreeNode<>();
            node.value = nodeData[index];
            node.left = createTree(nodeData, nullFlag, 2 * index + 1);
            node.right = createTree(nodeData, nullFlag, 2 * index + 2);
            return node;
        }
        return null;
    }
    public TreeNode<T> createTree(T nullFlag, int index){
        return createTree(nodeData, nullFlag, index);
    }
    /**
     * 按序添加树节点
     * @param root
     * @param node
     * @return
     */
    public TreeNode<T> addTreeNode(TreeNode<T> root, TreeNode<T> node){
        if (nodeData.length < 1){
            return node;
        }
        int length = nodeData.length;
        List<Integer> flag = new ArrayList<>();
        int div = 0;
        while (length > 0){
            div = (length - 1) % 2;
            length = (length - 1) / 2;
            flag.add(0, div);
        }
        TreeNode<T> tempRoot = root;
        for (int i = 0; i < flag.size() - 1; i++){
            if (flag.get(i) == 0){
                tempRoot = tempRoot.left;
            }else
                tempRoot = tempRoot.right;
        }
        if (flag.get(flag.size() - 1) == 0){
            tempRoot.left = node;
        }else
            tempRoot.right = node;
        nodeData = Arrays.copyOf(nodeData, nodeData.length + 1);
        nodeData[nodeData.length - 1] = node.value;
        return root;
    }

    // 树所有节点
    TreeNode<T>[] nodeDataList;
    // 类似图的创建方法
    public TreeUtil(TreeNode<T>[] nodeDataList, int type) {
        this.nodeDataList = nodeDataList;
    }
    public TreeNode<T> createTree(Integer[][] construct){
        if (nodeDataList.length < 1)
            return null;
        for (Integer[] arr : construct){
            if(arr[1] != null){
                nodeDataList[arr[0] - 1].left = nodeDataList[arr[1] - 1];
            }
            if(arr[2] != null){
                nodeDataList[arr[0] - 1].right = nodeDataList[arr[2] - 1];
            }
        }
        return nodeDataList[construct[0][0] - 1];
    }

    // 前序遍历
    List<T> preOrderList = new ArrayList<>();
    /**
     * 前序遍历
     * @param root 根节点
     * @return 遍历结果链表
     */
    public List<T> preOrder(TreeNode<T> root) {
        if (root != null){
            preOrderList.add(root.getValue());
            preOrder(root.left);
            preOrder(root.right);
        }
        return preOrderList;
    }

    List<T> preOrderListNoneRecursion = new ArrayList<>();
    /**
     * 非递归前序遍历-1
     * 需要利用栈记录遍历过的节点
     * @param root
     * @return
     */
    public List<T> preOrderNoneRecursion(TreeNode<T> root) {
        Stack<TreeNode<T>> s = new Stack<>();
        while (root != null){
            while(root != null){
                preOrderListNoneRecursion.add(root.getValue());
                s.push(root);
                root = root.left;
            }
            if (s.isEmpty()){
                root = null;
            }else {
                root = s.pop();
            }

            while(root != null && root.right == null){
                if (s.isEmpty()){
                    root = null;
                }else {
                    root = s.pop();
                }
            }
            if(root != null)
                root = root.right;
        }
        return preOrderListNoneRecursion;
    }
    List<T> preOrderListNoneRecursion2 = new ArrayList<>();
    /**
     * 非递归前序遍历-2
     * 需要利用栈记录遍历过的节点
     * 利用栈是否为null的条件
     * @param root
     * @return
     */
    public List<T> preOrderNoneRecursion2(TreeNode<T> root) {
        Stack<TreeNode<T>> s = new Stack<>();
        while (root != null || !s.isEmpty()){
            if(root == null){
                root = s.pop();
                root = root.right;
                continue;
            }
            s.push(root);
            preOrderListNoneRecursion2.add(root.getValue());
            root = root.left;
        }
        return preOrderListNoneRecursion2;
    }

    // 中序遍历
    List<T> midOrderList = new ArrayList<>();
    public List<T> midOrder(TreeNode<T> root){
        if(root != null){
            midOrder(root.left);
            midOrderList.add(root.value);
            midOrder(root.right);
        }
        return midOrderList;
    }


    List<T> midOrderListNoneRecursion = new ArrayList<>();

    /**
     * 非递归中序遍历-1
     * @param root
     * @return
     */
    public List<T> midOrderNoneReursion(TreeNode<T> root){
        Stack<TreeNode<T>> s = new Stack<>();
        while(root != null){
            while(root != null){
                s.push(root);
                root = root.left;
            }
            if (s.isEmpty()){
                root = null;
            }else{
                root = s.pop();
                midOrderListNoneRecursion.add(root.getValue());
            }
            while(root != null && root.right == null){
                if(s.isEmpty()){
                    root = null;
                }else{
                    root = s.pop();
                    midOrderListNoneRecursion.add(root.getValue());
                }
            }
            if(root != null)
                root = root.right;
        }

        return midOrderListNoneRecursion;
    }
    List<T> midOrderListNoneRecursion2 = new ArrayList<>();
    /**
     * 非递归中序遍历-2
     * @param root
     * @return
     */
    public List<T> midOrderNoneReursion2(TreeNode<T> root){
        Stack<TreeNode<T>> s = new Stack<>();
        while (root != null || !s.isEmpty()){
            if(root == null){
                root = s.pop();
                midOrderListNoneRecursion2.add(root.getValue());
                root = root.right;
                continue;
            }
            s.push(root);
            root = root.left;
        }
        return midOrderListNoneRecursion2;
    }

    // 后序遍历
    List<T> afterOrderList = new ArrayList<>();
    public List<T> afterOrder(TreeNode<T> root) {
        if (root != null){
            afterOrder(root.left);
            afterOrder(root.right);
            afterOrderList.add(root.getValue());
        }
        return afterOrderList;
    }

    List<T> afterOrderListNoneRecursion = new ArrayList<>();

    /**
     * 非递归后序遍历-1
     * @param root
     * @return
     */
    public List<T> afterOrderNoneRecursion(TreeNode<T> root) {
        TreeNode<T> preNode = null;
        Stack<TreeNode<T>> s = new Stack<>();
        s.push(root);
        while(root != null) {
            while (root != null) {
                if (root.right != null) {
                    s.push(root.right);
                }
                if (root.left != null) {
                    s.push(root.left);
                }
                root = root.left;
            }
            if(s.isEmpty()){
                root = null;
            }else{
                root = s.pop();
            }
            while((root != null && root.left == null && root.right == null) || (root != null && root.right == preNode || root != null && root.left == preNode)){
                afterOrderListNoneRecursion.add(root.getValue());
                preNode = root;
                if(s.isEmpty()){
                    root = null;
                }else{
                    root = s.pop();
                }
            }
            if(root != null){
                s.push(root);
                //root = root.right;
            }
        }
        return afterOrderListNoneRecursion;
    }

    List<T> afterOrderListNoneRecursion2 = new ArrayList<>();
    /**
     * 非递归后序遍历-2
     * 关键思想:
     * 该节点的左右都为空或者左、右节点已经遍历，则该节点就可以被遍历了，否则将先将右节点入栈，再将左节点入栈
     * @param root
     * @return
     */
    public List<T> afterOrderNoneRecursion2(TreeNode<T> root) {
        TreeNode<T> preNode = null;
        Stack<TreeNode<T>> s = new Stack<>();
        s.add(root);
        while(!s.isEmpty()){
            TreeNode<T> curNode = s.peek();
            if((curNode.left == null && curNode.right==null) || (curNode.left == preNode || curNode.right == preNode)){
                preNode = s.pop();
                afterOrderListNoneRecursion2.add(preNode.getValue());
            }else{
                if(curNode.right != null){
                    s.push(curNode.right);
                }
                if(curNode.left != null){
                    s.push(curNode.left);
                }
            }
        }
        return afterOrderListNoneRecursion2;
    }

    // 层次遍历
    // 辅助队列
    List<TreeNode> levelOrderList = new ArrayList<>();
    public List<TreeNode> levelOrder(TreeNode<T> root){
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()){
            TreeNode currentNode = q.poll();
            levelOrderList.add(currentNode);
            if (currentNode.left != null){
                q.add(currentNode.left);
            }
            if (currentNode.right != null){
                q.add(currentNode.right);
            }
        }
        return levelOrderList;
    }

    public static void main(String[] args){

        Integer[] t = new Integer[]{1, 2, 3, 4, 5, 6};
        TreeUtil<Integer> tu = new TreeUtil<>(t);
        TreeNode<Integer> root = tu.createTree(Integer.MAX_VALUE, 0);
        /*List<Integer> preOrder = tu.preOrder(root);
        List<Integer> midOrder = tu.midOrder(root);
        List<Integer> atfterOrder = tu.afterOrder(root);
        tu.addTreeNode(root, new TreeNode<>(7));
        tu.addTreeNode(root, new TreeNode<>(8));
        tu.addTreeNode(root, new TreeNode<>(9));

        System.out.println("end");
        List<TreeNode<Integer>> treeNodeList = new ArrayList<>();
        treeNodeList.add(new TreeNode<>(1));
        treeNodeList.add(new TreeNode<>(2));
        treeNodeList.add(new TreeNode<>(3));
        treeNodeList.add(new TreeNode<>(4));
        treeNodeList.add(new TreeNode<>(5));
        treeNodeList.add(new TreeNode<>(6));
        Integer[][] cons = new Integer[][]{{1, 2, 3},{2, 4, 5}, {3, 6, null}};
        TreeUtil<Integer> tu2 = new TreeUtil(treeNodeList.toArray(new TreeNode[0]), 0);
        TreeNode<Integer> root2 = tu2.createTree(cons);
        List<Integer> preOrder2 = tu2.preOrder(root2);*/

        List<Integer> preOrderListNoneRecursion = tu.preOrderNoneRecursion(root);
        List<Integer> preOrderListNoneRecursion2 = tu.preOrderNoneRecursion2(root);

        List<Integer> midOrderListNoneRecursion = tu.midOrderNoneReursion(root);
        List<Integer> midOrderListNoneRecursion2 = tu.midOrderNoneReursion2(root);

        List<Integer> afterOrderListNoneRecursion = tu.afterOrderNoneRecursion(root);
        List<Integer> afterOrderListNoneRecursion2 = tu.afterOrderNoneRecursion2(root);


        System.out.println("end2");
    }

}
